﻿#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<assert.h>
using namespace std;
//日期类;
class Date
{ 
public:
	//构造函数;
	Date(int year=1, int month=1, int day=1)
		: _year(year)
		,_month(month)
		,_day(day)
	{}
	//拷贝构造;
	Date(const Date& date)
	{
		_year = date._year;
		_month = date._month;
		_day = date._day;
	}
	int GetMonthDay()
	{
		static int arr[13] = { -1,31,28,31,30,31,30,31,31,30,31,30,31 };
		if (_month == 2 && (((_year % 4 == 0) && (_year % 100 != 0)) || (_year % 400 == 0)))
			return 29;
		return arr[_month];
	}
	void print()
	{
		cout << _year << " " << _month << " " << _day << endl;
	}
	// 赋值运算符重载
	Date& operator=(const Date& d)
	{
		_year = d._year;
		_month = d._month;
		_day = d._day;
		return *this;
	}
	// 析构函数
	~Date()
	{}
	// 日期+=天数
	Date& operator+=(int day)
	{
		_day += day;
		while (_day > GetMonthDay())
		{
			_day -= GetMonthDay();
			_month++;
			if (_month==13)
			{
				_month = 1;
				_year++;
			}
		}
		return *this;
	}
	// 日期+天数
	Date operator+(int day)
	{
		Date tem = *this;
		tem += day;
		return *this;
	}

	//// 日期+天数
	//Date operator+(int day)
	//{
	//	Date tem = *this;
	//	tem._day += day;
	//	while (tem._day > GetMonthDay())
	//	{
	//		tem._day -= GetMonthDay();
	//		tem._month++;
	//		if (tem._month == 13)
	//		{
	//			tem._month = 1;
	//			tem._year++;
	//		}
	//	}
	//	return tem;
	//}
	////// 日期+=天数
	//Date& operator+=(int day)
	//{
	//	*this = *this + day;
	//	return *this;
	//}
	// 日期-天数
	Date operator-(int day)
	{
		Date tem = *this;
		tem -= day;
		return tem;
	}
	// 日期-=天数
	Date& operator-=(int day)
	{
		_day -= day;
		while (_day <= 0)
		{
			_month--;
			if (_month == 0)
			{
				_year--;
				_month = 12;
			}
			_day += GetMonthDay();
		}
		return *this;
	}
	// 前置++
	Date& operator++()
	{
		_day++;
		if (_day > GetMonthDay())
		{
			_day = 1;
			_month++;
		}
		return *this;
	}
	// 后置++
	Date operator++(int)
	{
		Date tem = *this;
		++(*this);
		return tem;
	}
	// 后置--
	Date operator--(int)
	{
		Date tem = *this;
		--(*this);
		return tem;
	}
	// 前置--
	Date& operator--()
	{
		*this -= 1;
		return *this;
	}
	// >运算符重载
	bool operator>(const Date& d)
	{
		if (_year == d._year)
		{
			if (_month == d._month)
			{
				if (_day > d._day)
					return true;
				else
					return false;
			}
			else if (_month > d._month)
				return true;
			else
				return false;
		}
		else if (_year > d._year)
			return true;
		else
			return false;
	}
	// ==运算符重载
	bool operator==(const Date& d)
	{
		return (_year == d._year) && (_month == d._month) && (_day == d._day);
	}
	// >=运算符重载
	bool operator >= (const Date& d)
	{
		return (*this > d) || (*this == d);
	}
	// <运算符重载
	bool operator < (const Date& d)
	{
		return !(*this >= d);
	}
	// <=运算符重载
	bool operator <= (const Date& d)
	{
		return !(*this > d);
	}
	// !=运算符重载
	bool operator != (const Date& d)
	{
		return !(*this==d);
	}
	// 日期-日期 返回天数
	int operator-(const Date& d)
	{		
		Date big = *this;
		Date small = d;
		int ret = 0;
		if (big < small)
		{
			big = d;
			small = *this;
		}
		while (small < big)
		{
			ret++;
			++small;
		}
		return ret;
	}
private:
	int _year;
	int _month;
	int _day;
};





                      //string模拟实现;
//namespace kang
//{
//	class string
//	{
//	public:
//		typedef char* iterator;
//		typedef const char* const_iterator;
//		void swap(string& s)
//		{
//			std::swap(_str, s._str);
//			std::swap(_capacity, s._capacity);
//			std::swap(_size, s._size);
//		}
//		void print()
//		{
//			for (int i = 0; i < _size; i++)
//			{
//				cout << _str[i] << " ";
//			}
//			cout << endl;
//			auto it = cbegin();
//			while (it != cend())
//			{
//				cout << *it << " ";
//				it++;
//			}
//			cout << endl;
//		}
//		//构造函数;
//		string(const char* str="")
//		{
//			int len = strlen(str);
//			_size = len;
//			//capacity中不包含'\0'；
//			_capacity = _size;
//			_str = new char[len+1];
//			strcpy(_str, str);
//		}
//		////拷贝构造;
//		//string(const string& s)
//		//{
//		//	delete[] _str;
//		//	char* tmp = new char[s._capacity];
//		//	int i = 0;
//		//	//注意'/0'问题;
//		//	while (i <= s._size)
//		//	{
//		//		tmp[i] = s[i];
//		//		i++;
//		//	}
//		//	std::swap(_str, tmp);
//		//	_size = s._size;
//		//	_capacity = s._capacity;
//		//}
//		// 
//		// 
//		// 复制重载;
//		//string operator=(const string& s)
//		//{
//		//	if (this != &s)
//		//	{
//		//		delete[]_str;
//		//		char* tmp = new char[s._capacity + 1];
//		//		strcpy(tmp, s._str);
//		//		_str = tmp;
//		//		_size = s._size;
//		//		_capacity = s._capacity;
//		//	}
//		//	return *this;
//		//}
//
//		//拷贝构造,现代写法;
//		string(const string& s)
//		{
//			string tmp(s._str);
//			swap(tmp);
//		}
//		//复制重载,现代写法;
//		string operator=(string tmp)
//		{
//			swap(tmp);
//			return *this;
//		}
//		~string()
//		{
//			delete[] _str;
//		}
//		char operator[](int i)const 
//		{
//			return _str[i];
//		}
//		char* c_str()
//		{
//			return _str;
//		}
//		const char* c_str()const 
//		{
//			return _str;
//		}
//		const_iterator cbegin()const
//		{
//			return _str;
//		}
//
//		const_iterator cend()const 
//		{
//			return _str+_size;
//		}
//		iterator begin()
//		{
//			return _str;
//		}
//
//		iterator end()
//		{
//			return _str + _size;
//		}
//		// capacity
//		size_t size()const
//		{
//			return _size;
//		}
//
//		size_t capacity()const
//		{
//			return _capacity;
//		}
//		bool empty()
//		{
//			return _size == 0;
//		}
//		void resize(size_t n, char c = '\0')
//		{ 
//			if (n > _size)
//			{   
//				//如果大于容器的容量，就需要扩容;
//				if (n > _capacity)
//				{
//					reserve(n);
//				}
//				memset(_str+_size, c, n - _size);
//			}
//			//n小于当前size，删除元素;
//			else
//			{
//				_str[n] = '\0';
//				memset(_str, c, n);
//			}
//		}
//		void reserve(size_t n)
//		{
//			//扩容；
//			if (n>_capacity)
//			{
//				char* tmp = new char[n + 1];
//				strcpy(tmp, _str);
//				delete[]_str;
//				_str = tmp;
//				_capacity = n;
//			}
//		}
//		// modify
//		void push_back(char c)
//		{
//			if (_size == _capacity)
//			{
//				reserve(_capacity == 0 ? 4 : 2 * _capacity);
//			}
//			_str[_size++] = c;
//			_str[_size] = '\0';
//		}
//		string& operator+=(char c)
//		{
//			push_back(c);
//			return *this;
//		}
//		void append(const char* str)
//		{ 
//			int len = strlen(str);
//			if (_size + len >= _capacity)
//			{
//				reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
//			}
//			int i = 0;
//			while (i < len)
//			{
//				push_back(str[i]);
//				i++;
//			}
//		}
//		void clear()
//		{
//			_size = 0;
//			_str[_size] = '\0';
//		}
//		bool operator<(const string& s)
//		{
//			return strcmp(_str, s._str) < 0;
//		}
//
//		bool operator<=(const string& s)
//		{
//			return !(*this > s);
//		}
//
//		bool operator>(const string& s)
//		{
//			return !(*this <= s);
//		}
//
//		bool operator>=(const string& s)
//		{
//			return !(*this < s);
//		}
//
//		bool operator==(const string& s)
//		{
//			return strcmp(_str, s._str) == 0;
//		}
//
//		bool operator!=(const string& s)
//		{
//			return !(*this == s);
//		}
//
//		// 返回c在string中第一次出现的位置
//		int find(const string& s, char c)
//		{
//			for (int i = 0; i < s.size(); i++)
//			{
//				if (s[i] == c)
//					return i;
//			}
//			return -1;
//		}
//		// 返回子串s在string中第一次出现的位置
//		size_t find(const char* s, size_t pos = 0) const;
//
//		// 在pos位置上插入字符c/字符串str
//		string& insert(size_t pos, char c)
//		{
//			if (_size == _capacity)
//				reserve(_capacity == 0 ? 4 : 2 * _capacity);
//			for (size_t i = _size+1; i > pos; i--)
//			{
//				_str[i] = _str[i - 1];
//			}
//			_str[pos] = c;
//			_size++;
//			return *this;
//		}
//
//		string& insert(size_t pos, const char* str)
//		{
//			size_t len = strlen(str);
//			if (len + _size > _capacity)
//				reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
//			for (int i = _size + len; i >= len + pos; i--)
//			{
//				_str[i] = _str[i - len];
//			}
//			for (int i = 0; i < len; i++)
//			{
//				_str[pos + i] = str[i];
//			}
//			_size += len;
//			return *this;
//		}
//		// 删除pos位置上的len个元素;
//		string& erase(size_t pos, size_t len)
//		{
//			for (int i = pos+len; i <= _size; i++)
//			{
//				_str[i - len] = _str[i];
//			}
//			_size -= len;
//			return *this;
//		}
//	private:
//		char* _str=nullptr;
//		int _size=0;
//		int _capacity=0;
//	};
//}
//static int a = 0;
//static int add(int x, int y)
//{
//	return x + y;
//}

              ////////////////////////vector
//namespace kang
//{
//	template<class T>
//	class vector
//	{
//	public:
//		typedef T* iterator;
//		typedef const T* const_iterator;
//		iterator begin()
//		{
//			return _start;
//		}
//		iterator end()
//		{
//			return _finish;
//		}
//		const_iterator cbegin()const
//		{
//			return _start;
//		}
//		const_iterator cend()const
//		{
//			return _finish;
//		}
//		//构造函数;
//		vector()
//			:_start(nullptr)
//			,_finish(nullptr)
//			,_endOfStorage(nullptr)
//		{}
//		vector(int n, const T& value = T())
//		{
//			_start = new T[n];
//			_finish = _start + n;
//			for (int i = 0; i < n; i++)
//			{
//				_start[i] = value;
//			}
//			_endOfStorage = _finish;
//		}
//		template<class InputIterator>
//		vector(InputIterator start, InputIterator end)
//		{
//			int i = 0;
//			_start = new T[end - start];
//			while (start != end)
//			{
//				_start[i++] = *start;
//				start++;
//			}
//			_finish = _start + i;
//			_endOfStorage = _finish;
//		}
//
//		//拷贝构造;
//		vector(const vector<T>& v)
//			:_start(v._start)
//			,_finish(v._finish)
//			,_endOfStorage(v._endOfStorage)
//		{
//			_start = new T[v.size()];
//			for (int i = 0; i < v.size(); i++)
//			{
//				_start[i] = v[i];
//			}
//			_finish = _start + v.size();
//			_endOfStorage = _finish;
//		}
//		//复制重载;
//		vector<T>& operator=(vector<T> tmp)
//		{
//			swap(tmp);
//			return *this;
//		}
//		~vector()
//		{
//			delete[] _start;
//			_start = nullptr;
//			_endOfStorage = _finish = nullptr;
//		}
//		void swap(vector<T>& v)
//		{
//			std::swap(_start, v._start);
//			std::swap(_finish, v._finish);
//			std::swap(_endOfStorage, v._endOfStorage);
//		}
//		T& operator[](int i)
//		{
//			return _start[i];
//		}
//		const T& operator[](int i)const
//		{
//			return _start[i];
//		}
//		int size()const 
//		{
//			return _finish-_start;
//		}
//		int capacity()const 
//		{
//			return _endOfStorage-_start;
//		}
//		//扩容，只影响容器的容量;
//		void reserve(size_t n)
//		{
//			if (n > capacity())
//			{
//				int old_size = _finish - _start;
//				//开辟新空间;
//				T* tmp = new T[n];
//				int i = 0;
//				//拷贝数据;
//				while (i < _finish - _start)
//				{
//					tmp[i] = _start[i];
//					i++;
//				}
//				delete[]_start;
//				_start = nullptr;
//				std::swap(_start,tmp);
//				_finish = _start + old_size;
//				_endOfStorage = _start + n;
//			}
//		}
//		//改变容器的数据的大小，也可能改变容量的大小;
//		void resize(size_t n, const T& value = T())
//		{
//			if (n > _finish - _start)
//			{
//				//小于capacity；
//				if (n <= _endOfStorage - _start)
//				{
//					int size = _finish - _start;
//					int i = 0;
//					while (i + size < n)
//					{
//						_start[i + size] = value;
//						i++;
//					}
//				}
//				//扩容;
//				else
//				{
//					reserve(n);
//
//				}
//			}
//			else
//			{
//				_finish = _start + n;
//			}
//		}
//		void push_back(const T& x)
//		{
//			if (_finish == _endOfStorage)
//			{
//				reserve(capacity()==0 ? 4 : 2 * capacity());
//			}
//			_start[size()] = x;
//			_finish++;
//		}
//		void pop_back()
//		{
//			_finish--;
//		}
//		iterator insert(iterator pos, const T& x)
//		{
//
//			if (_finish == _endOfStorage)
//			{
//				//扩容后pos会失效，所以要保存；
//				int oldpos = pos - _start;
//				reserve(capacity() == 0 ? 4 : 2 * capacity());
//				pos = _start + oldpos;
//			}
//			auto it = end();
//			while (it > pos)
//			{
//				*it = *(it - 1);
//				it--;
//			}
//			*pos = x;
//			_finish++;
//			return pos;
//		}
//		iterator erase(iterator pos)
//		{
//			assert(size() > 0);
//			auto it = pos;
//			while (it < _finish - 1)
//			{
//				*it = *(it + 1);
//				it++;
//			}
//			--_finish;
//			return pos;
//		}
//	private:
//		iterator _start; //指向数组的头；
//		iterator _finish;//指向有效数据的尾;
//		iterator _endOfStorage;//指向容器容量的尾
//	};
//}



/////////////////////////////////////list
//template<class Container>
//void print_container(Container& con)
//{
//	//for (int i = 0; i < (int)con.size(); i++)
//	//{
//	//	cout << con[i] << " ";
//	//}
//	//cout << endl;
//	for (auto e : con)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}


           //////////////////////list模拟实现;
//namespace kang
//{
//	template<class T>
//	struct ListNode
//	{
//		//构造函数；
//		ListNode(const T& value = T())
//			:_val(value)
//			, _prev(nullptr)
//			, _next(nullptr)
//		{}
//		T _val;
//		ListNode<T>* _prev;
//		ListNode* _next;
//	};
//	template<class T,class Ref,class Ptr>
//	struct Iterator
//	{
//		typedef Iterator<T, Ref, Ptr> Self;
//		typedef ListNode<T> Node;
//		Iterator(Node* it = nullptr)
//			:_it(it)
//		{}
//		Self operator++()
//		{
//			_it=_it->_next;
//			return *this;
//		}
//		Self operator--()
//		{
//			_it=_it->_prev;
//			return *this;
//		}
//		Ref operator*()
//		{
//			return _it->_val;
//		}
//		Ptr operator->()
//		{
//			return &_it->_val;
//		}
//		bool operator!=(const Self& l)
//		{
//			return _it != l._it;
//		}
//		bool operator==(const Self& l)
//		{
//			return !(*this != l);
//		}
//		Node* _it;
//	};
//	template<class T>
//	class list
//	{
//	public:
//		typedef ListNode<T> Node;
//		typedef Iterator<T, T&, T*> iterator;
//		typedef Iterator<const T, const T& , const T*> const_iterator;
//		//构造函数;
//		list()
//		{
//			_head = new Node(-1);
//			_head->_next = _head->_prev = _head;
//		}
//		list(int n, const T& value = T())
//			:list() //委托构造,只能在初始化列表中使用;
//		{
//			while (n--)
//			{
//				push_back(value);
//			}
//		}
//		template<class iter>
//		list(iter first, iter finish)
//			:list()
//		{
//			while (first != finish)
//			{
//				push_back(*first);
//				++first;
//			}
//		}
//		//拷贝构造;
//		list(list<T>& lt)
//		{
//			list<T> tmp(lt.begin(), lt.end());
//			_head = nullptr;
//			swap(tmp);
//		}
//		list<T>& operator=(list<T> lt)
//		{
//			swap(lt);
//			return *this;
//		}
//		~list()
//		{
//			if (!_head)
//			{
//				Node* del = _head->_next;
//				while (del != _head)
//				{
//					Node* next = del->_next;
//					del->_next = del->_prev = nullptr;
//					delete[]del;
//					del = next;
//				}
//				_head->_next = _head->_prev = nullptr;
//				delete[]_head;
//			}
//		}
//		//如果不传引用会导致无穷递归;
//		void swap(list<T>& lt)
//		{
//			std::swap(lt._head, _head);
//		}
//		iterator begin()
//		{
//			return iterator(_head->_next); 
//		}
//		iterator end() 
//		{
//			return iterator(_head);
//		}
//		const_iterator cbegin()const
//		{
//			return const_iterator(_head->_next);
//		}
//		const_iterator cend()const
//		{
//			return const_iterator(_head);
//		}
//		size_t size()const
//		{
//			int ret = 0;
//			if (!_head)
//				return 0;
//			Node* cur = _head->_next;
//			while (cur != _head)
//			{
//				cur = cur->_next;
//				ret++;
//			}
//			return ret;
//		}
//		bool empty()const
//		{
//			return _head->_next == _head->_prev;
//		}
//		//void push_back(const T& val)
//		//{
//		//	iterator it = _head->_prev;
//		//	Node* newnode = new Node(val);
//		//	Node* tail = _head->_prev;
//		//	tail->_next = newnode;
//		//	newnode->_prev =tail;
//		//	_head->_prev = newnode;
//		//	newnode->_next = _head;
//		//}
//		T& front()
//		{
//			return _head->_next->_val;
//		}
//		const T& front()const
//		{
//			return _head->_next->_val;
//		}
//		T& back()
//		{
//			return _head->_prev->_val;
//		}
//		const T& back()const
//		{
//			return _head->_prev->_val;
//		}
//		// 在pos位置前插入值为val的节点
//		iterator insert(iterator pos, const T& val)
//		{
//			Node* cur = pos._it;
//			Node* prev = cur->_prev;
//			Node* newnode = new Node(val);
//			//插入;
//			prev->_next = newnode;
//			newnode->_next = cur;
//			newnode->_prev = prev;
//			cur->_prev = newnode;
//			return pos;
//		}
//		// 删除pos位置的节点
//		iterator erase(iterator pos)
//		{
//			Node* del = pos._it;
//			Node* prev = del->_prev;
//			Node* next = del->_next;
//			del->_next = del->_prev = nullptr;
//			delete[]del;
//			prev->_next = next;
//			next->_prev = prev;
//			pos._it = next;
//			return pos;
//		}
//		void push_back(const T& val) { insert(end(), val); }
//		void pop_back() { erase(--end()); }
//		void push_front(const T& val) { insert(begin(), val); }
//		void pop_front() { erase(begin()); }
//		//清除数据，不清理资源;
//		void clear()
//		{
//			iterator it = begin();
//			while (it != end())
//			{
//				erase(it);
//				++it;
//			}
//			_head->_next = _head->_prev = nullptr;
//		}
//	private:
//		Node* _head;
//	};
//}
//////////////////////////重写昨天bug较多的代码;
//namespace kang
//{
//	template<class T>
//	struct ListNode
//	{
//		ListNode(const T& value=T())
//			:_val(value)
//			,_prev(nullptr)
//			,_next(nullptr)
//		{}
//		T _val;
//		ListNode<T>* _prev;
//		ListNode<T>* _next;
//	};
//	template<class T,class Ref,class Ptr>
//	struct Iterator
//	{
//		typedef ListNode<T> Node;
//		typedef Iterator<T, Ref, Ptr> Self;
//		Iterator(Node* _node = nullptr)
//			:_it(_node)
//		{
//		}
//		Self& operator++()
//		{
//			_it = _it->_next;
//			return *this;
//		}
//		Self operator++(int)
//		{
//			Node* tmp = _it;
//			_it = _it->_next;
//			return tmp;
//		}
//		Self& operator--()
//		{
//			_it = _it->_prev;
//			return *this;
//		}
//		Self operator--(int)
//		{
//			Node* tmp = _it;
//			_it = _it->_prev;
//			return tmp;
//		}
//		Ref& operator*()
//		{
//			return _it->_val;
//		}
//		Ptr operator->()
//		{
//			return &_it->_val;
//		}
//		bool operator==(Self& it)const
//		{
//			return _it == (it._it);
//		}
//		bool operator!=(Self& it)const
//		{
//			return !(*this == it);
//		}
//
//		Node* _it;
//	};
//	template<class T>
//	class list
//	{
//		typedef ListNode<T> Node;
//		typedef Iterator<T, T&, T*> iterator;
//		typedef Iterator<const T, const T&, const T*> const_iterator;
//	public:
//		list()
//		{
//			_head = new Node(-1);
//			_head->_next = _head->_prev = _head;
//		}
//		iterator begin()
//		{
//			return iterator(_head->_next);
//		}
//		iterator end()
//		{
//			return iterator(_head);
//		}
//		const_iterator cbegin()const
//		{
//			return const_iterator(_head->_next);
//		}
//		const_iterator cend()const
//		{
//			return const_iterator(_head->_prev);
//		}
//		iterator insert(iterator pos, const T& value)
//		{
//			Node* newnode = new Node(value);
//			Node* prev = pos._it->_prev;
//			prev->_next = newnode;
//			newnode->_prev = prev;
//			newnode->_next = pos._it;
//			pos._it->_prev = newnode;
//			return pos;
//		}
//		iterator erase(iterator pos)
//		{
//			Node* del = pos._it;
//			Node* prev = del->_prev;
//			Node* next = del->_next;
//			del->_next = del->_prev = nullptr;
//			delete[] del;
//			prev->_next = next;
//			next->_prev = prev;
//			return pos;
//		}
//	private:
//		Node* _head;
//	};
//}
//template<class Container>
//void print_container(Container& con)
//{
//	//for (int i = 0; i < (int)con.size(); i++)
//	//{
//	//	cout << con[i] << " ";
//	//}
//	//cout << endl;
//	for (auto e : con)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//
/////////////////////优先级队列模拟实现：
//namespace kang
//{
//	template<class T>
//	struct Less
//	{
//		bool operator()(const T& t1, const T& t2)
//		{
//			return t1 < t2;
//		}
//	};
//	template<class T,class Container=vector<T>,class Compare=Less<T>>
//	class priority_queue
//	{
//	public:
//		priority_queue() = default;
//		template<class Iterator>
//		priority_queue(Iterator first,Iterator finish)
//		{
//			while (first != finish)
//			{
//				push_back(*first);
//				first++;
//			}
//		}
//		bool empty()const
//		{
//			return _con.empty();
//		}
//		size_t size()const
//		{
//			return _con.size();
//		}
//		T& top()const
//		{
//			return _con.front[0];
//		}
//		void push_back(const T& value)
//		{
//			int size = _con.size();
//			_con.push_back(value);
//			AdjustUp(_con,size);
//		}
//		void AdjustUp(Container& con,int size)
//		{
//			int child = size;
//			int parent = (child - 1) / 2;
//			Compare com;
//			while (child > 0)
//			{
//				if (com(con[parent], con[child]))
//				{
//					std::swap(con[parent], con[child]);
//					child = parent;
//					parent = (child - 1) / 2;
//				}
//				else
//				{
//					break;
//				}
//			}
//		}
//		void pop()
//		{
//			std::swap(_con[0], _con[_con.size() - 1]);
//			int end = _con.size() - 2;
//			AdjustDown(_con, 0, end);
//			_con.pop_back();
//		}
//		void AdjustDown(Container& con,int parent,int end)
//		{
//			Compare com;
//			int child = parent * 2 + 1;
//			while (child <= end && child + 1 < end)
//			{
//				if (com(con[child], con[child + 1])&&child+1<end)
//				{
//					child++;
//				}
//				if (com(con[parent], con[child]))
//				{
//					std::swap(con[child], con[parent]);
//					parent = child;
//					child = parent * 2 + 1;
//				}
//				else
//				{
//					break;
//				}
//			}
//		}
//	private:
//		Container _con;
//		Compare _compare;
//	};
//}
//
//
//namespace kang
//{
//	template<class T>
//	struct BSTreeNode
//	{
//		BSTreeNode(const T& value)
//			:_left(nullptr)
//			,_right(nullptr)
//			,_parent(nullptr)
//			,_val(value)
//		{}
//		BSTreeNode<T>* _left;
//		BSTreeNode<T>* _right;
//		BSTreeNode<T>* _parent;
//		T _val;
//	};
//	template<class T>
//	class BSTree
//	{
//	public:
//		typedef BSTreeNode<T> Node;
//		BSTree()
//			:_root(nullptr)
//		{}
//		bool Insert(const T& value)
//		{
//			if (_root == nullptr)
//			{
//				_root = new Node(value);
//				return true;
//			}
//			Node* parent = nullptr;
//			Node* cur = _root;
//			while (cur)
//			{
//				if (cur->_val < value)
//				{
//					parent = cur;
//					cur = cur->_right;
//				}
//				else if (cur->_val > value)
//				{
//					parent = cur;
//					cur = cur->_left;
//				}
//				else
//				{
//					return false;
//				}
//			}
//			//开始插入;
//			cur = new Node(value);
//			if (parent->_val < cur->_val)
//				parent->_right = cur;
//			else
//				parent->_left = cur;
//			cur->_parent = parent;
//			return true;
//		}
//		bool Erase(const T& value)
//		{
//			if (_root == nullptr)
//				return false;
//			Node* cur = _root;
//			Node* parent = _root;
//			while (cur)
//			{
//				if (cur->_val < value)
//				{
//					parent = cur;
//					cur = cur->_right;
//				}
//				else if (cur->_val > value)
//				{
//					parent = cur;
//					cur = cur->_left;
//				}
//				else
//				{
//					//开始删除;
//					//1.左右子树都为空：
//					if (cur->_left == nullptr && cur->_right == nullptr)
//					{
//						if (parent->_left == cur)
//							parent->_left = nullptr;
//						else
//							parent->_right = nullptr;
//						cur->_parent = nullptr;
//						delete[]cur;
//					}
//					//左为空;
//					else if (cur->_left == nullptr)
//					{
//						parent->_left = cur->_right;
//						cur->_right->_parent = parent;
//						cur->_parent = nullptr;
//						delete[]cur;
//					}
//					//右为空;
//					else if (cur->_right == nullptr)
//					{
//						parent->_left = cur->_left;
//						cur->_left->_parent = parent;
//						cur->_parent = nullptr;
//						delete[]cur;
//					}
//					//左右都不为空：
//					else
//					{
//						Node* del = cur;
//						//找左子树的最右节点;
//						parent = cur;
//						cur = cur->_left;
//						while (cur->_right)
//						{
//							parent = cur;
//							cur = cur->_right;
//						}
//						parent->_val = cur->_val;
//						if (cur->_left)
//						{
//							parent->_left = cur->_left;
//						}
//					}
//					cur = nullptr;
//					return true;
//				}
//			}
//			return false;
//		}
//		void InOrder()
//		{
//			_InOrder(_root);
//		}
//	private:
//		void _InOrder(Node* _root)
//		{
//			if (_root == nullptr)
//				return;
//			_InOrder(_root->_left);
//			cout << _root->_val << " ";
//			_InOrder(_root->_right);
//		}
//		Node* _root;
//	};
//}
//
//void print(vector<int>&nums)
//{
//	for (auto e : nums)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//排序算法;

//void Insert(vector<int>& nums)
//{
//	int size = nums.size();
//	//[0,i]有序;
//	for (int i = 0; i < nums.size()-1; i++)
//	{
//		int end = i + 1;
//		int tmp = nums[end];
//		while (end>0)
//		{
//			if (end>0&&nums[end - 1] > tmp)
//			{
//				nums[end] = nums[end - 1];
//				end--;
//			}
//			else
//			{
//				break;
//			}
//		}
//		nums[end] = tmp;
//	}
//}


//稳定，n^2;
//void Insert(vector<int>& nums)
//{
//	int size = nums.size();
//	for (int i = 0; i < nums.size() - 1; i++)
//	{
//		int end = i;//[0,end]有序;
//		int tmp = nums[end+1];
//		while (end>=0)
//		{
//			if (nums[end] > tmp)
//			{
//				nums[end + 1] = nums[end];
//				end--;
//			}
//			else
//			{
//				break;
//			}
//		}
//		nums[end + 1] = tmp;
//	}
//}
//
//
////不稳定，n^1.25;
//void XiEr(vector<int>& nums)
//{
//	int size = nums.size();
//	int gap = 7;
//	while (gap > 1)
//	{
//		gap = gap / 3 + 1;
//		for (int i = 0; i < nums.size() - gap; i += gap)
//		{
//			int end = i;
//			int tmp = nums[end + gap];
//			while (end >= 0)
//			{
//				if (nums[end] > tmp)
//				{
//					nums[end+gap] = nums[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			nums[end + gap] = tmp;
//		}
//	}
//}

//int GetMid(vector<int>& a, int left, int right)
//{
//	int mid = (left + right) / 2;
//	if (a[left] < a[mid])
//	{
//		if (a[mid] < a[right])
//		{
//			return mid;
//		}
//		else if (a[right] < a[left])
//		{
//			return left;
//		}
//		else
//		{
//			return right;
//		}
//	}
//	else
//	{
//		if (a[mid] > a[right])
//		{
//			return mid;
//		}
//		else if (a[right] > a[left])
//		{
//			return left;
//		}
//		else
//		{
//			return right;
//		}
//	}
//}
//void Qsort(vector<int>& nums,int left,int right)
//{
//	if (left >= right) return;
//	int begin = left, end = right;
//	int keyi = GetMid(nums, left, right);
//	swap(nums[left], nums[keyi]); // 基准值交换到左端
//	int tmp = nums[left];         // 基准值
//	while (begin < end)
//	{
//		while (begin < end && nums[end] >= tmp)
//		{
//			end--;
//		}
//		while (begin < end && nums[begin] <= tmp)
//		{
//			begin++;
//		}
//		swap(nums[begin], nums[end]);
//	}
//	swap(nums[left], nums[begin]);
//	Qsort(nums, left, begin - 1);
//	Qsort(nums, begin + 1, right);
//}


//递归方式;
//不稳定，nlogn~n^2;
//void Qsort(vector<int>& nums, int left, int right)
//{
//	if (left >= right) return;
//
//	int begin = left, end = right;
//	int keyi = left;
//	int key = nums[keyi];
//	while (begin < end)
//	{
//		while (begin < end && nums[end] >= key) end--;
//		while (begin < end && nums[begin] <= key) begin++;
//		swap(nums[begin],nums[end]);
//	}
//	swap(nums[begin], nums[keyi]);
//	Qsort(nums, left, begin - 1);
//	Qsort(nums, begin + 1, right);
//}
//
////快排非递归方式;
////不稳定  nlogn~n^2   空间:logn~n
//#include<stack>
//void F_Qsort(vector<int>& nums, int left, int right)
//{
//	stack<int> st;
//	st.push(right);
//	st.push(left);
//	while (!st.empty())
//	{
//		int begin = st.top();
//		st.pop();
//		int end = st.top();
//		st.pop();
//		int keyi = begin;
//		int key = nums[keyi];
//		//开始进行排序;
//		while (begin < end)
//		{
//			while (begin < end && nums[end] >= key) end--;
//			while (begin < end && nums[begin] <= key) begin++;
//			swap(nums[begin], nums[end]);
//		}
//		swap(nums[keyi], nums[begin]);
//		//[left,begin-1][begin+1,right];
//		if (left < begin - 1)
//		{
//			st.push(begin - 1);
//			st.push(left);
//		}
//		if (right > begin + 1)
//		{
//			st.push(right);
//			st.push(begin + 1);
//		}
//	}
//}
//
////归并;  稳定;
//vector<int> tmp(5);
//void MergeSort(vector<int>&nums, vector<int>& tmp,int left,int right)
//{
//	if (left >= right) return;
//	int mid = left + (right - left) / 2;
//	//递归归并;
//	//[left,mid] [mid+1,right];
//	MergeSort(nums,tmp, left, mid);
//	MergeSort(nums,tmp, mid + 1, right);
//	int begin1 = left, end1 = mid;
//	int begin2 = mid + 1, end2 = right;
//	int i = 0;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (nums[begin1] <= nums[begin2])
//		{
//			tmp[left + i] = nums[begin1];
//			begin1++;
//			i++;
//		}
//		else
//		{
//			tmp[left + i] = nums[begin2];
//			begin2++;
//			i++;
//		}
//	}
//	//出循环，一个数组走完;
//	while (begin1 <= end1)
//	{
//		tmp[left + i] = nums[begin1];
//		begin1++;
//		i++;
//	}
//	while (begin2 <= end2)
//	{
//		tmp[left + i] = nums[begin2];
//		begin2++;
//		i++;
//	}
//	//拷贝到原数组;
//	for (int j = left; j < i + left; j++)
//	{
//		nums[j] = tmp[j];
//	}
//}

//template<class K>
//struct BSTreeNode
//{
//	BSTreeNode(K val=K())
//		:_val(val)
//		,_left(nullptr)
//		,_right(nullptr)
//	{
//	}
//	BSTreeNode<K>* _left = nullptr;
//	BSTreeNode<K>* _right = nullptr;
//	K _val;
//};
//template<class K>
//class BSTree
//{
//public:
//	using Node = BSTreeNode<K>;
//public:
//	BSTree() = default;
//	//不允许插入相同元素;(map和set)
//	bool Insert(K val)
//	{
//		Node* newnode = new Node(val);
//		if (_root == nullptr)
//		{
//			_root = newnode;
//			return true;
//		}
//		Node* cur = _root;
//		Node* parent = nullptr;
//		while (cur)
//		{
//			if (cur->_val < val)
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (cur->_val > val)
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				return false;
//			}
//		}
//		//出循环，cur的位置及要插入的位置;
//		if (val > parent->_val)
//		{
//			parent->_right = newnode;
//		}
//		else
//		{
//			parent->_left = newnode;
//		}
//		return true;
//	}

	//////////////代码冗余;
	//bool erase(K val)
	//{
	//	assert(_root);
	//	Node* cur = _root;
	//	Node* parent = nullptr;
	//	while (cur)
	//	{
	//		if (val < cur->_val)
	//		{
	//			parent = cur;
	//			cur = cur->_left;
	//		}
	//		else if (val > cur->_val)
	//		{
	//			parent = cur;
	//			cur = cur->_right;
	//		}
	//		//找到开始删除;
	//		else
	//		{
	//			//1.删除节点左右两边都是空;
	//			if (cur->_left == nullptr && cur->_right == nullptr)
	//			{
	//				//当要删除的节点正好是根;
	//				if (cur == _root)
	//				{
	//					delete _root;
	//					_root = nullptr;
	//				}
	//				//要删除的节点不是根;
	//				else
	//				{
	//					if (parent->_left == cur)
	//					{
	//						parent->_left = nullptr;
	//					}
	//					else
	//					{
	//						parent->_right = nullptr;
	//					}
	//					delete cur;
	//					cur = nullptr;
	//				}
	//			}
	//			//2.删除节点左子树或者右子树不为空;
	//			else if (cur->_left==nullptr || cur->_right==nullptr)
	//			{
	//				//删除根节点;
	//				if (parent == nullptr)
	//				{
	//					Node* del = _root;
	//					if (cur->_left)
	//					{
	//						_root = cur->_left;
	//					}
	//					else
	//					{
	//						_root = cur->_right;
	//					}
	//					del->_left = del->_right = nullptr;
	//					delete del;
	//				}
	//				//删除不是根节点;
	//				else
	//				{
	//					if (parent->_left == cur)
	//					{
	//						if (cur->_left)
	//						{
	//							parent->_left = cur->_left;
	//						}
	//						else
	//						{
	//							parent->_left = cur->_right;
	//						}
	//					}
	//					else
	//					{
	//						if (cur->_left)
	//						{
	//							parent->_right = cur->_left;
	//						}
	//						else
	//						{
	//						}
	//						delete cur;
	//						cur->_left = cur->_right = nullptr;
	//					}
	//				}
	//			}
	//			//3.左右都不为空;
	//			else
	//			{
	//				Node* lr = cur->_left;
	//				Node* lrp = cur;
	//				//找左子树的最右节点;
	//				while (lr->_right)
	//				{
	//					lrp = lr;
	//					lr = lr->_right;
	//				}

	//				//1
	//				if (lrp == cur)
	//				{
	//					lr->_right = cur->_right;
	//					lr->_right = cur->_right;
	//				}
	//				//2
	//				else
	//				{
	//					lrp->_right = lr->_left;
	//					lr->_left = cur->_left;
	//					lr->_right = cur->_right;
	//					
	//				}

	//				if (parent&&parent->_left == cur)
	//				{
	//					parent->_left = lr;
	//				}
	//				if(parent && parent->_right==cur)
	//				{
	//					parent->_right = lr;
	//				}
	//				if (cur == _root) _root = lr;
	//				cur->_left = cur->_right = nullptr;
	//				delete cur;
	//			}
	//			return true;
	//		}
		//}
		//return false;
	//} 
//     bool erase(K val)
//    {
//		 Node* cur = _root;
//		 Node* parent = nullptr;
//		 while (cur)
//		 {
//			 if (val < cur->_val)
//			 {
//				 parent = cur;
//				 cur = cur->_left;
//			 }
//			 else if (val < cur->_val)
//			 {
//				 parent = cur;
//				 cur = cur->_right;
//			 }
//			 //找到节点开始删除;
//			 else
//			 {
//				 //优化,删除可分四种情况(左右孩子是否为空);
//
//				 //根据孩子数量又可分为两种：0~1  2
//
//				 //1.情况1，孩子数量为0或者1个,此时直接删除，调整链接关系即可;
//				 if (cur->_left == nullptr)
//				 {
//					 //左孩子为空或者左右都为空;
//					 if (parent == nullptr)
//					 {
//						 _root = cur->_right;
//					 }
//					 else
//					 {
//						 if (parent->_left == cur)
//						 {
//							 parent->_left = cur->_right;
//						 }
//						 else
//						 {
//							 parent->_right = cur->_right;
//						 }
//					 }
//				 }
//				 //删除节点右孩子为空
//				 else if(cur->_right==nullptr)
//				 {
//					 if (parent == nullptr)
//					 {
//						 _root = cur->_left;
//						 delete cur;
//					 }
//					 else
//					 {
//						 if (parent->_left == cur)
//						 {
//							 parent->_left = cur->_left;
//						 }
//						 else
//						 {
//							 parent->_right = cur->_left;
//						 }
//					 }
//				 }
//				 //2.左右都不为空;
//				 else
//				 {
//					 Node* lrp = cur;
//					 Node* lr = cur->_left;
//					 while (lr->_right)
//					 {
//						 lrp = lr;
//						 lr = lr->_right;
//					 }
//					 //替换法;
//					 cur->_val = lr->_val;
//					 //链接lrp和lr
//					 if (lrp->_left == lr)
//					 {
//						 lrp->_left = lr->_left;
//					 }
//					 else
//					 {
//						 lrp->_right = lr->_left;
//					 }
//					 delete lr;
//				 }
//				 return true;
//			 }
//		 }
//		 return false;
//	  }
//		void Inorder()
//		{
//			_inorder(_root);
//		}
//		bool empty()
//		{
//			return _root == nullptr;
//		}
//	private:
//		void _inorder(Node * _root)
//		{
//			if (_root == nullptr) return;
//			//中序遍历;
//			_inorder(_root->_left);
//			cout << _root->_val << "->";
//			_inorder(_root->_right);
//		}
//	public:
//		Node* _root = nullptr;
//};






//AVLTree
//template<class K, class V>
//struct AVLTreeNode
//{
//	AVLTreeNode(const pair<K,V>& kv)
//		:_left(nullptr)
//		,_right(nullptr)
//		,_parent(nullptr)
//		,_kv(kv)
//		,_bf(0)
//	{}
//	AVLTreeNode<K, V>* _left;
//	AVLTreeNode<K, V>* _right;
//	AVLTreeNode<K, V>* _parent;
//	pair<K, V> _kv;
//	int _bf;//平衡因子;
//};
//
//template<class K,class V>
//class AVLTree
//{
//public:
//	using Node = AVLTreeNode<K, V>;
//	AVLTree() = default;
//	bool Insert(const pair<K, V>& kv)
//	{
//		if (_root == nullptr)
//		{
//			_root = new Node(kv);
//			return true;
//		}
//		Node* cur = _root;
//		Node* parent = nullptr;
//		while (cur)
//		{
//			if (cur->_kv.first < kv.first)
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if(cur->_kv.first>kv.first)
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				return false;
//			}
//		}
//		cur = new Node(kv);
//		//出循环，代表插入合法，此时cur就是插入的位置;
//		//插入;
//		if (parent->_kv.first<kv.first)
//		{
//			parent->_right = cur;
//		}
//		else
//		{
//			parent->_left = cur;
//		}
//		cur->_parent = parent;
//		//根据平衡因子进行分情况讨论;
//		while (parent)
//		{
//			//更新平衡因子;
//			if (cur == parent->_left) parent->_bf--;
//			else parent->_bf++;
//			//-1到0，或者是1到0,此时不用调整;
//			if (parent->_bf == 0)
//			{
//				break;
//			}
//			//原来parent左右平衡，插入后左右差一，向上看看是否要更新;
//			else if (parent->_bf == -1 || parent->_bf == 1)
//			{
//				cur = parent;
//				parent = parent->_parent;
//			}
//			//bf为2或者-2，说明本来就差一，插入到更高的一侧更加不平衡了，此时需要旋转;
//			else if(parent->_bf==-2 || parent->_bf==2)
//			{
//				//1.右单旋;
//				if (parent->_bf == -2 && cur->_bf == -1)
//				{
//					RouteR(parent);
//				}
//				//2.左单旋;
//				else if (parent->_bf == 2 && cur->_bf == 1)
//				{
//					RouteL(parent);
//				}
//				//3.左右单旋;
//				else if (parent->_bf == -2 && cur->_bf == 1)
//				{
//					RouteLR(parent);
//				}
//				//4.右左双旋;
//				else
//				{
//					RouteRL(parent);
//
//				}
//				break;
//			}
//			else
//			{
//				assert(false);
//			}
//		}
//		return true;
//	}
//
//	//右单旋;
//	void RouteR(Node*parent)
//	{
//		Node* cur = parent->_left;
//		parent->_left = cur->_right;
//		Node* grandparent = parent->_parent;
//		if (grandparent == nullptr)
//		{
//			_root = cur;
//			cur->_parent = nullptr;
//		}
//		else
//		{
//			cur->_parent = grandparent;
//			if (grandparent->_left == parent) grandparent->_left = cur;
//			else grandparent->_right = cur;
//		}
//		parent->_parent = cur;
//		if (cur->_right)
//		{
//			cur->_right->_parent = parent;
//		}
//		cur->_right = parent;
//
//		parent->_bf = cur->_bf = 0;
//	}
//	void RouteL( Node* parent)
//	{
//		Node* cur = parent->_right;
//		parent->_right = cur->_left;
//		Node* grandparent = parent->_parent;
//		if (grandparent == nullptr)
//		{
//			_root = cur;
//			cur->_parent = nullptr;
//		}
//		else
//		{
//			cur->_parent = grandparent;
//			if (grandparent->_left == parent) grandparent->_left = cur;
//			else grandparent->_right = cur;
//		}
//		parent->_parent = cur;
//		if (cur->_left)
//		{
//			cur->_left->_parent = parent;
//		}
//		cur->_left = parent;
//		//更新平衡因子
//		parent->_bf = cur->_bf = 0;
//	}
//	void RouteRL(Node* parent)
//	{
//		Node* subR = parent->_right;
//		Node* subRL = subR->_left;
//		int bf = subRL->_bf;
//		RouteR(parent->_right);
//		RouteL(parent);
//
//		//调整平衡因子;
//		if (bf == 0)
//		{
//			subR->_bf = 0;
//			subRL->_bf = 0;
//			parent->_bf = 0;
//		}
//		else if (bf == 1)
//		{
//			subR->_bf = 0;
//			subRL->_bf = 0;
//			parent->_bf = -1;
//		}
//		else if (bf == -1)
//		{
//			subR->_bf = 1;
//			subRL->_bf = 0;
//			parent->_bf = 0;
//		}
//		else
//		{
//			assert(false);
//		}
//	}
//	void RouteLR(Node* parent)
//	{
//		Node* subL = parent->_left;
//		Node* subLR = subL->_right;
//		int bf = subLR->_bf;
//		RouteL(parent->_left);
//		RouteR(parent);
//		//调整平衡因子;
//		if (bf == 0)
//		{
//			subL->_bf = 0;
//			subLR->_bf = 0;
//			parent->_bf = 0;
//		}
//		else if (bf == -1)
//		{
//			subL->_bf = 0;
//			subLR->_bf = 0;
//			parent->_bf = 1;
//		}
//		else if (bf == 1)
//		{
//			subL->_bf = -1;
//			subLR->_bf = 0;
//			parent->_bf = 0;
//		}
//		else
//		{
//			assert(false);
//		}
//	}
//	void Inroder()
//	{
//		_inorder(_root);
//		cout << endl;
//	}
//	int _Height(Node* root)
//	{
//		if (root == nullptr)
//			return 0;
//		int leftHeight = _Height(root->_left);
//		int rightHeight = _Height(root->_right);
//		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
//	}
//	bool IsBalanceTree()
//	{
//		return _IsBalanceTree(_root);
//	}
//	bool _IsBalanceTree(Node* root)
//	{
//		// 空树也是AVL树
//		if (nullptr == root)
//			return true;
//		// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差
//		int leftHeight = _Height(root->_left);
//		int rightHeight = _Height(root->_right);
//		int diff = rightHeight - leftHeight;
//		//如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者
//		// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树
//		if (abs(diff) >= 2)
//		{
//			cout << root->_kv.first<<" " << "高度差异常" << endl;
//			return false;
//		}
//		if (root->_bf != diff)
//		{
//			cout << root->_kv.first << "平衡因子异常" << endl;
//			return false;
//		}
//		// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
//		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
//	}
//private:
//	void _inorder(Node* root)
//	{
//		if (root == nullptr) return;
//		_inorder(root->_left);
//		cout << root->_kv.first << " ";
//		_inorder(root->_right);
//	}
//public:
//	Node* _root = nullptr;
//};
//
//
//
//
//
//
//
////红黑树;
//enum COLOR
//{
//	RED,
//	BLACK
//};
//template<class K,class V>
//struct RBTreeNode
//{
//	RBTreeNode(const pair<K,V>& kv)
//		:_left(nullptr)
//		,_right(nullptr)
//		,_parent(nullptr)
//		,_kv(kv)
//		,_color(RED)
//	{}
//	RBTreeNode<K, V>* _left;
//	RBTreeNode<K, V>* _right;
//	RBTreeNode<K, V>* _parent;
//	pair<K, V> _kv;
//	COLOR	_color;
//};
//
//
//template<class K,class V>
//class RBTree
//{
//public:
//	using Node = RBTreeNode<K, V>;
//	RBTree() = default;
//	bool insert(const pair<K, V>& kv)
//	{
//		Node* parent = nullptr;
//		Node* cur = _root;
//		if (_root == nullptr)
//		{
//			_root = new Node(kv);
//			_root->_color = BLACK;
//			return true;
//		}
//		while (cur)
//		{
//			if (cur->_kv.first < kv.first)
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (cur->_kv.first > kv.first)
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				return false;
//			}
//		}
//		//出循环，代表插入合法；
//		cur = new Node(kv);
//		cur->_color = RED;
//		if (parent->_kv.first < kv.first) parent->_right = cur;
//		else  parent->_left = cur;
//		cur->_parent = parent;
//		while (parent && parent->_color == RED)
//		{
//			Node* grandparent = parent->_parent;
//			//按照uncle在左还是右分类;
//
//			//1.uncle在右;
//			if (grandparent->_left == parent)
//			{
//				Node* uncle = grandparent->_right;
//				//1.uncle存在且为红：只染色不旋转;
//				if (uncle && uncle->_color == RED)
//				{
//					parent->_color = uncle->_color = BLACK;
//					grandparent->_color = RED;
//
//					//向上更新(因为此时grandparent是红色)
//					cur = parent;
//					parent = grandparent;
//					grandparent = parent->_parent;
//
//					//更新到根节点停止更新;
//					if (parent == _root)
//					{
//						parent->_color = BLACK;
//						return true;
//					}
//				}
//				//2.uncle不存在或为黑:旋转+变色;
//				else
//				{
//					//单旋;
//					if (parent->_left == cur)
//					{
//						RouteR(grandparent);
//						parent->_color = BLACK;
//						grandparent->_color = RED;
//					}
//					//双旋;
//					else
//					{
//						RouteL(grandparent);
//						RouteR(grandparent);
//						cur->_color = BLACK;
//						grandparent->_color = RED;
//					}
//					break;
//				}
//			}
//
//			//2.uncle在左;
//			else
//			{
//				Node* uncle = grandparent->_left;
//				//uncle存在且为红，只变色;
//				if (uncle && uncle->_color == RED)
//				{
//					parent->_color = uncle->_color = BLACK;
//					grandparent->_color = RED;
//
//					//向上更新;(因为grandparent为红)
//					cur = parent;
//					parent = grandparent;
//					grandparent = parent->_parent;
//
//					if (parent == _root)
//					{
//						parent->_color = BLACK;
//						return true;
//					}
//				}
//				//uncle不存在或为黑;
//				else 
//				{
//					//单旋;
//					if (parent->_right == cur)
//					{
//						RouteL(grandparent);
//						parent->_color = BLACK;
//						grandparent->_color = RED;
//					}
//					//双旋;
//					else
//					{
//						RouteR(grandparent);
//						RouteL(grandparent);
//						cur->_color = BLACK;
//						grandparent->_color = RED;
//					}
//					break;
//				}
//			}
//		}
//		return true;
//	}
//	//右单旋;
//	void RouteR(Node* parent)
//	{
//		Node* cur = parent->_left;
//		parent->_left = cur->_right;
//		Node* grandparent = parent->_parent;
//		if (grandparent == nullptr)
//		{
//			_root = cur;
//			cur->_parent = nullptr;
//		}
//		else
//		{
//			cur->_parent = grandparent;
//			if (grandparent->_left == parent) grandparent->_left = cur;
//			else grandparent->_right = cur;
//		}
//		parent->_parent = cur;
//		if (cur->_right)
//		{
//			cur->_right->_parent = parent;
//		}
//		cur->_right = parent;
//	}
//	void RouteL(Node* parent)
//	{
//		Node* cur = parent->_right;
//		parent->_right = cur->_left;
//		Node* grandparent = parent->_parent;
//		if (grandparent == nullptr)
//		{
//			_root = cur;
//			cur->_parent = nullptr;
//		}
//		else
//		{
//			cur->_parent = grandparent;
//			if (grandparent->_left == parent) grandparent->_left = cur;
//			else grandparent->_right = cur;
//		}
//		parent->_parent = cur;
//		if (cur->_left)
//		{
//			cur->_left->_parent = parent;
//		}
//		cur->_left = parent;
//	}
//	void RouteRL(Node* parent)
//	{
//		Node* subR = parent->_right;
//		Node* subRL = subR->_left;
//		int bf = subRL->_bf;
//		RouteR(parent->_right);
//		RouteL(parent);
//	}
//	void RouteLR(Node* parent)
//	{
//		Node* subL = parent->_left;
//		Node* subLR = subL->_right;
//		int bf = subLR->_bf;
//		RouteL(parent->_left);
//		RouteR(parent);
//	}
//	bool Check(Node* root, int blackNum, const int refNum)
//	{
//		if (root == nullptr)
//		{
//			// 前序遍历⾛到空时，意味着⼀条路径⾛完了
//			//cout << blackNum << endl;
//			if (refNum != blackNum)
//			{
//				cout << "存在⿊⾊结点的数量不相等的路径" << endl;
//				return false;
//			}
//			return true;
//		}
//		// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了
//		if (root->_col == RED && root->_parent->_col == RED)
//		{
//			cout << root->_kv.first << "存在连续的红⾊结点" << endl;
//			return false;
//		}
//		if (root->_col == BLACK)
//		{
//			blackNum++;
//		}
//		return Check(root->_left, blackNum, refNum)
//			&& Check(root->_right, blackNum, refNum);
//	}
//	bool IsBalance()
//	{
//		if (_root == nullptr)
//			return true;
//		if (_root->_col == RED)
//			return false;
//		// 参考值
//		int refNum = 0;
//		Node* cur = _root;
//		while (cur)
//		{
//			if (cur->_col == BLACK)
//			{
//				++refNum;
//			}
//			cur = cur->_left;
//		}
//		return Check(_root, 0, refNum);
//	}
//private:
//	Node* _root = nullptr;
//};



//1137:第n个斐波那契数;
//class Solution {
//public:
//	int tribonacci(int n)
//	{
//		if (n == 0) return 0;
//		if (n == 1) return 1;
//		if (n == 2) return 1;
//		vector<int>dp(n + 1);
//		dp[0] = 0;
//		dp[1] = 1;
//		dp[2] = 1;
//		for (int i = 3; i < n + 1; i++)
//		{
//			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
//		}
//		return dp[n];
//	}
//};
//
////散步问题：
//class Solution {
//public:
//	int waysToStep(int n)
//	{
//		vector<long long>dp(n + 1);
//		if (n == 1) return 1;
//		if (n == 2) return 2;
//		if (n == 3) return 4;
//		dp[0] = 0;
//		dp[1] = 1;
//		dp[2] = 2;
//		dp[3] = 4;
//		for (int i = 4; i < n + 1; i++)
//		{
//			dp[i] = dp[i - 1] % 1000000007 + dp[i - 2] % 1000000007 + dp[i - 3] % 1000000007;
//		}
//		return dp[n] % 1000000007;
//	}
//};



//746爬楼梯最小消费;
//class Solution {
//public:
//	int minCostClimbingStairs(vector<int>& cost)
//	{
//		vector<int>dp(cost.size() + 1, 0);//dp[i]表示到i层所需要的最小花费；
//		for (int i = 2; i < cost.size(); i++)
//		{
//			dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
//
//		}
//		int ret = min(dp[cost.size() - 1] + cost[cost.size() - 1], dp[cost.size() - 2] + cost[cost.size() - 2]);
//		return ret;
//	}
//};
//int main()
//{
//	vector<int>dp({ 10,15,20 });
//	int ret=minCostClimbingStairs(dp);
//	cout << ret;
//	return 0;
//}